當今天遇到一個情況是，事件間是有依賴性/方向性(B事件發生前一定要A事件)，譬如說排課系統，有些課會有需要預修的課(譬如說，要修電磁學前要修過微積分、線性代數、工程數學等等，否則會上得有點辛苦，這種有方向性的依賴關係)，這時候我們可以用拓樸排序來幫助我們排程。拓樸排序是用來排有向性的非循環圖(directed acyclic graph)。這個我覺得我們先從圖解說在來看程式碼會比較容易理解(圖 1)。我們從A看 -> 發現B和E依賴它 -> 看B -> 發現C依賴它 -> 看C -> 發現D依賴它 -> 看G(沒有人依賴它) -> 把G放入stack 並標示為visited(拜訪過的意思) -> 再回頭看D (G已經被標過) -> 將D放入stack並標是為visited -> 將C放入stack並標示為visited......以此類推for剩下的-> B -> E -> A -> F。

圖1 拓樸排序範例，所以排序完就會是F-> A -> E-> B -> C -> D -> G。 這樣完全不會違背我們的方向規則。

# defaultdict和python內建的dictionary的差別在，當key不存在時，defaultdict不會return keyError，他會幫你加上key，然後value為你自已設的預設值，在這個例子裡，我們的預設值為一空白的list

from collections import defaultdict

class Graph:
    # 跟前面製作graph的方法一樣
    def __init__(self):
        self.graph = defaultdict(list)
        
    def insertedge(self, v1, v2):
        self.graph[v1].append(v2)

    def __str__(self):
        res = ''
        for key, value in self.graph.items():
            res += f'{key}:{value}\n'
        return res
    # 這邊我們需要一個helper function 讓他在裡面遞迴
    def topologicalsort(self):
        stack = []
        visited = []
     #這邊如果我們寫成self.graph.keys()會出現error message因為self.graphs的key會在topohelper裡增加   
        for k in list(self.graph):
            if k not in visited:
                self.topohelper(k, visited, stack)
        print(stack)

    def topohelper(self, k, visited, stack):
        visited.append(k)
        for v in self.graph[k]:
            if v not in visited:
                self.topohelper(v, visited, stack)
        stack.insert(0, k)


customGraph = Graph()

customGraph.insertedge('A', 'B')
customGraph.insertedge('A', 'E')
customGraph.insertedge('F', 'E')
customGraph.insertedge('B', 'C')
customGraph.insertedge('C', 'D')
customGraph.insertedge('E', 'D')
customGraph.insertedge('D', 'G')
customGraph.topologicalsort()
>> ['F', 'A', 'E', 'B', 'C', 'D', 'G']
print(customGraph)
>>  A:['B', 'E']
    F:['E']
    B:['C']
    C:['D']
    E:['D']
    D:['G']
    G:[]

參考資料:
The Complete Data Structures and Algorithms Course in Python (Udemy)有興趣的話可以自己上去看看。